﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace SCG.General
{
    public class PathFinder
    {
        //constructor
        public PathFinder(IPathRegion region)
        {
            _region = region;
        }

        //public properties
        public IPathRegion Region
        {
            get
            {
                return _region;
            }
        }

        //find best path
        public Path FindPath(SCGPoint from, SCGPoint to, int costLimit)
        {
            _zones.Clear();
            _examinedZones.Clear();

            //add source zone
            Path path = new Path(this);
            path.Zones.Add(from);

            //if source = dest, we're done
            if (from.EqualsPoint(to))
                return path;

            //remember best path so far
            Path bestPath = null;
            int bestPathCost = Int32.MaxValue;

            //keep track of developing paths
            List<Path> developingPaths = new List<Path>();
            developingPaths.Add(path);

            //start examining neighbors
            while (developingPaths.Count > 0)
            {
                List<Path> testPaths = new List<Path>(developingPaths);
                developingPaths.Clear();
                foreach (Path testPath in testPaths)
                {
                    SCGPoint lastZone = testPath.LastZone;
                    List<SCGPoint> neighbors = _region.GetNeighbors(lastZone);
                    foreach (SCGPoint neighbor in neighbors)
                    {
                        //don't consider zones already examined
                        if (testPath.Zones.ContainsPoint(neighbor))
                            continue;
                        if (_examinedZones.ContainsPoint(neighbor))
                            continue;

                        //create a new path by adding this zone to the end of the old one
                        Path newPath = new Path(this, neighbor, testPath);
                        if (newPath.Cost <= costLimit)
                        {
                            //is it the destination?
                            if (neighbor.EqualsPoint(to))
                            {
                                //we found a route, is it better than the best one we found so far?
                                if (newPath.Cost < bestPathCost)
                                {
                                    bestPath = newPath;
                                    bestPathCost = newPath.Cost;
                                }
                            }
                            else
                            {
                                //it's still developing, keep for next iteration, if it's worthwhile
                                if (newPath.Cost < bestPathCost)
                                {
                                    developingPaths.Add(newPath);
                                    _examinedZones.Add(neighbor);
                                }
                            }
                        }
                    }
                }
            }
            return bestPath;
        }

        //private members
        private IPathRegion _region;
        private List<SCGPoint> _zones = new List<SCGPoint>();
        private List<SCGPoint> _examinedZones = new List<SCGPoint>();
    }
}
